package com.ihr360.expr.core.graph;

import com.ihr360.expr.core.GraphCycleException;
import com.ihr360.expr.core.GraphCycleExceptionType;
import com.ihr360.expr.engine.GraphTraversalListener;
import com.ihr360.expr.engine.VariableID;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.CopyOnWriteArraySet;

public class Graph implements Iterable {
    final Logger logger = LoggerFactory.getLogger(Graph.class.getName());
    private boolean wantsEdges = true;
    //顶点
    private Set<VariableID> nodes = new CopyOnWriteArraySet<>();
    private Set<Edge> edges = new CopyOnWriteArraySet<>();
    /**
     * 出边
     */
    private Map<VariableID, Set<Edge>> outbounds = new ConcurrentHashMap<>();
    /**
     * 入边
     */
    private Map<VariableID, Set<Edge>> inbounds = new ConcurrentHashMap<>();
    /**
     * 图的排序
     */
    private List ordered = null;
    /**
     * 遍历过的节点
     */
    private Set traversed = null;

    public void setIncludeEdges(boolean include) {
        this.wantsEdges = include;
    }

    public void add(VariableID node) {
        nodes.add(node);
    }

    public Set<Edge> getInbounds(VariableID node) {
        return inbounds.get(node);
    }

    public Set<Edge> getOutbounds(VariableID node) {
        return outbounds.get(node);
    }

    public void clearOutbounds(VariableID node) {
        Set<Edge> s = outbounds.get(node);
        if (s != null) {
            Iterator<Edge> i = s.iterator();
            while (i.hasNext()) {
                remove(i.next());
            }
        }
    }

    public void clearInbounds(VariableID node) {
        Set<Edge> s = inbounds.get(node);
        if (s != null) {
            Iterator<Edge> i = s.iterator();
            while (i.hasNext()) {
                remove(i.next());
            }
        }
    }

    public void remove(VariableID node) {
        nodes.remove(node);
        clearInbounds(node);
        clearOutbounds(node);
    }

    public void add(Edge e) throws GraphCycleException {
        checkCycle(e);
        nodes.add(e.source);
        nodes.add(e.target);
        edges.add(e);
        Set<Edge> in = inbounds.get(e.target);
        if (in == null) {
            inbounds.put(e.target, in = new CopyOnWriteArraySet<>());
        }
        in.add(e);
        Set<Edge> out = outbounds.get(e.source);
        if (out == null) {
            outbounds.put(e.source, out = new CopyOnWriteArraySet<>());
        }
        out.add(e);
    }

    public void checkCycle(Edge e) throws GraphCycleException {
        Set visited = new CopyOnWriteArraySet();
        visited.add(e.source);
        //logger.debug("{} {}",visited.size(), e.source.getVariableId());
        checkCycle(e, visited);
    }

    private void checkCycle(Edge e, Set visited) throws GraphCycleException {
        //logger.debug("{} {}",visited.size(), e.target.getVariableId());
        if (visited.contains(e.target)) {
            throw new GraphCycleException(GraphCycleExceptionType.COLUMN_SCOPE_GE, e.source.getVariableId(), e.target.getVariableId());
        }
        visited.add(e.target);
        Set<Edge> out = outbounds.get(e.target);
        if (out != null) {
            Iterator<Edge> i = out.iterator();
            Set branch = new CopyOnWriteArraySet();
            while (i.hasNext()) {
                branch.addAll(visited);
                Edge edge = i.next();
                checkCycle(edge, branch);
                branch.clear();
            }
        }
    }

    public void remove(Edge e) {
        edges.remove(e);
        Set<Edge> in = inbounds.get(e.target);
        if (in != null) {
            in.remove(e);
        }
        Set<Edge> out = outbounds.get(e.source);
        if (out != null) {
            out.remove(e);
        }
    }

    public void sort() {
        ordered = new CopyOnWriteArrayList<>();
        traversed = new CopyOnWriteArraySet();
        Iterator<VariableID> n = nodes.iterator();
        Set<VariableID> remains = new CopyOnWriteArraySet<>(nodes);

        // First traverse nodes without inbounds
        while (n.hasNext()) {
            VariableID variableID = n.next();
            Set<Edge> in = inbounds.get(variableID);
            if (in == null || in.isEmpty()) {
                traverse(variableID);
                remains.remove(variableID);
            }
        }

        // Now traverse the rest
        n = remains.iterator();
        while (n.hasNext()) {
            VariableID o = n.next();
            if (!traversed.contains(o)) {
                traverse(o);
            }
        }
    }

    private void traverse(VariableID node) {
        Set<Edge> in = inbounds.get(node);
        if (in != null) {
            Iterator<Edge> i = in.iterator();
            // if all inbounds haven't been traversed we must stop
            while (i.hasNext()) {
                Edge e = i.next();
                if (!traversed.contains(e.source)) {
                    return;
                } else if (wantsEdges) {
                    ordered.add(e);
                }
            }
        }

        if (!traversed.contains(node)) {
            traversed.add(node);
            ordered.add(node);
        }

        Set<Edge> out = outbounds.get(node);
        if (out == null || out.isEmpty()) {
            return;
        }

        Set avoid = new CopyOnWriteArraySet();

        Iterator<Edge> i = out.iterator();
        while (i.hasNext()) {
            Edge e = i.next();
            if (!traversed.contains(e)) {
                if (traversed.contains(e.target)) {
                    avoid.add(e.target);
                }
            }
        }

        i = out.iterator();
        while (i.hasNext()) {
            VariableID n = i.next().target;
            if (!avoid.contains(n)) {
                traverse(n);
            }
        }
    }

    public void clear() {
        edges.clear();
        inbounds.clear();
        outbounds.clear();
        nodes.clear();
        traversed = null;
        ordered.clear();
    }

    @Override
    public Iterator iterator() {
        if (ordered == null) {
            sort();
        }
        return ordered.iterator();
    }

    public void traverse(VariableID node, GraphTraversalListener listener) {
        Set<VariableID> subgraph = new CopyOnWriteArraySet<>();
        walk(node, subgraph);
        Set hs = new CopyOnWriteArraySet();
        hs.add(node);
        traverse(node, listener, hs, subgraph);
    }

    private void walk(VariableID node, Set traversed) {
        traversed.add(node);
        Set<Edge> out = outbounds.get(node);
        if (out != null) {
            Iterator<Edge> i = out.iterator();
            while (i.hasNext()) {
                Edge e = i.next();
                walk(e.target, traversed);
            }
        }
    }

    private void traverse(Object node, GraphTraversalListener listener,
                          Set traversed, Set<VariableID> subgraph) {
        Set<Edge> edges = outbounds.get(node);
        if (edges != null) {
            Iterator<Edge> i = edges.iterator();
            while (i.hasNext()) {
                Edge e = i.next();
                Set<Edge> ins = inbounds.get(e.target);
                Iterator<Edge> j = ins.iterator();
                boolean traverse = true;
                while (j.hasNext()) {
                    Edge in = j.next();
                    if (subgraph.contains(in.source) &&
                            !traversed.contains(in.source) &&
                            !node.equals(in.source)) {
                        traverse = false;
                        break;
                    }
                }
                if (traverse) {
                    listener.traverse(e.target);
                    traversed.add(e.target);
                    traverse(e.target, listener, traversed, subgraph);
                }
            }
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Iterator i = edges.iterator();
        while (i.hasNext()) {
            sb.append(i.next());
            sb.append("\n");
        }
        return sb.toString();
    }
}
